package _0639_Decode_Ways_II;

/**
 * Date: 2021/9/27 9:53
 * Content:
 * 执行用时：104 ms, 在所有 Java 提交中击败了6.13%的用户
 * 内存消耗：39.4 MB, 在所有 Java 提交中击败了38.04%的用户
 */
public class Solution {

    static final int MOD = (int)1e9 + 7;

    public int numDecodings(String s) {
        int n = s.length();
        int[] f = new int[n + 1];
        f[0] = 1;
        char[] cs = s.toCharArray();
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= 26; j++) {
                char a = cs[i - 1];  // 最后一位
                if (j <= 9) {
                    if (a == '*' || a == j + '0') f[i] = (f[i] + f[i - 1]) % MOD;
                } else if (i >= 2) {
                    char b = cs[i - 2];  // 倒数第二位
                    int y = j / 10, x = j % 10;
                    // * 不能代表0，因此必须要求y和x非零
                    if ((b == y + '0' || b == '*' && y != 0) && (a == x + '0' || a == '*' && x != 0))
                        f[i] = (f[i] + f[i - 2]) % MOD;
                }
            }
        return f[n];
    }

    public static void main(String[] args) {

        System.out.println((new Solution()).numDecodings("*"));  // 9
        System.out.println((new Solution()).numDecodings("**"));  // 96

        int res = 0;
        for (int i = 1; i <= 9; i++) res += (new Solution()).numDecodings(i + "*");
        System.out.println(res);  // 96
    }
}
